#include <iostream>
#include <chrono>

using namespace std;

// 递归实现
int FibonacciRecursive(int n) {
    if (n <= 1) {
        return n;
    } else {
        return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2);
    }
}

// 迭代实现
int FibonacciIterative(int n) {
    if (n <= 1) {
        return n;
    }

    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

int main() {
    const int n = 30;
    cout << "C++ Fibonacci(" << n << ")" << endl;

    // 测试递归实现
    auto start = std::chrono::high_resolution_clock::now();
    int fib_recursive = FibonacciRecursive(n);
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed_recursive = end - start;
    cout << "Recursive result: " << fib_recursive << endl;
    cout << "Recursive Execution time: " << elapsed_recursive.count() << " seconds" << endl;

    // 测试迭代实现
    start = std::chrono::high_resolution_clock::now();
    int fib_iterative = FibonacciIterative(n);
    end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed_iterative = end - start;
    cout << "Iterative result: " << fib_iterative << endl;
    cout << "Iterative Execution time: " << elapsed_iterative.count() << " seconds" << endl;

    return 0;
}